package com.gxc.array;

import java.util.*;

/**
 * 给定一个 N*3的矩阵 matrix，对于每一个长度为 3的小数组 arr，都表示一个大楼的三个数据。
 * arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。
 * 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 *
 * [举例]
 * matrix = {
 * {2,5,6},
 * {1,7,4},
 * {4,6,7},
 * {3,6,5},
 * {10,13,2},
 * {9,11,3},
 * {12,14,4},
 * {10,12,5}
 * }
 *
 * 返回:
 * {{1,2,4},
 * {2,4,6},
 * {4,6,7},
 * {6,7,4},
 * {9,10,3},
 * {10,12,5},
 * {12,14,4}}
 *
 * 解法：
 * 1.扫描线算法
 *
 */
public class BuildingOutline {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{2,5,6},
                {1,7,4},
                {4,6,7},
                {3,6,5},
                {10,13,2},
                {9,11,3},
                {12,14,4},
                {10,12,5}};
        List<List<Integer>> lists = process(matrix);
        System.out.println(lists);
    }

    public static List<List<Integer>> process(int[][] matrix) {
        Info[] nodes = buildNode(matrix);

        //坐标位置的最高高度
        TreeMap<Integer, Integer> indexHeightMap = new TreeMap<>();
        //坐标位置出现的所有高度集合
        TreeMap<Integer, Integer> heightTimesMap = new TreeMap<>();
        fillMap(indexHeightMap, heightTimesMap, nodes);

        return processMap(indexHeightMap);
    }

    /**
     * 每个坐标出现的高度
     * @param indexHeightMap
     * @return
     */
    private static List<List<Integer>> processMap(TreeMap<Integer,Integer> indexHeightMap) {
        List<List<Integer>> list = new ArrayList<>();

        Iterator<Map.Entry<Integer, Integer>> iterator = indexHeightMap.entrySet().iterator();
        int preIndex = indexHeightMap.firstKey();
        int preHeight = indexHeightMap.get(preIndex);
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            Integer key = next.getKey();
            Integer value = next.getValue();
            //如果高度发生变化
            if (value != preHeight) {
                //如果高度为0，则不添加
                if (preHeight!=0) {
                    List<Integer> indexHeight = new ArrayList<>(Arrays.asList(preIndex, key, preHeight));
                    list.add(indexHeight);
                }

                preIndex = key;
                preHeight= value;
            }

        }

        return list;
    }

    private static void fillMap(TreeMap<Integer,Integer> indexHeightMap, TreeMap<Integer,Integer> heightTimesMap, Info[] nodes) {
        for (Info node : nodes) {
            //坐标上升
            if (node.isadd) {
                if (heightTimesMap.containsKey(node.height)) {
                    heightTimesMap.put(node.height, heightTimesMap.get(node.height)+1);
                } else {
                    heightTimesMap.put(node.height, 1);
                }
            } else {
                //坐标下降
                //如果当前高度剩余一次，又是下降高度，则直接删除，否则高度出现的次数--
                if (heightTimesMap.get(node.height) == 1) {
                    heightTimesMap.remove(node.height);
                } else {
                    heightTimesMap.put(node.height, heightTimesMap.get(node.height)-1);
                }
            }
            //没有高度了
            int maxHeight = heightTimesMap.isEmpty()?0:heightTimesMap.lastKey();
            indexHeightMap.put(node.index, maxHeight);
        }
    }

    /**
     * 大楼高度转成上升或下降的坐标点
     * @param matrix
     * @return
     */
    private static Info[] buildNode(int[][] matrix) {
        Info[] infos = new Info[matrix.length*2];
        for (int i = 0; i < matrix.length; i++) {
            infos[i*2] = new Info(matrix[i][0], true, matrix[i][2]);
            infos[i*2+1] = new Info(matrix[i][1], false, matrix[i][2]);
        }

        Arrays.sort(infos, new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                if (o1.index != o2.index) return o1.index-o2.index;
                //同一坐标，维护上升的高度在前面
                return o1.isadd?-1:1;
            }
        });
        return infos;
    }


    public static class Info {

        public int index;
        //上升还是下降
        public boolean isadd;
        public int height;

        public Info(int index, boolean isadd, int height) {
            this.index = index;
            this.isadd = isadd;
            this.height = height;
        }
    }
}
